{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 变分量子振幅估算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Copyright (c) 2022 Institute for Quantum Computing, Baidu Inc. All Rights Reserved.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 概述"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本教程基于量桨实现单量子比特变分量子振幅估算（Variational Quantum Amplitude Estimation, VQAE）[1] 。在研究变分量子振幅估算前，首先介绍量子振幅估算是什么问题。\n",
    "\n",
    "假设一个作用在$n+1$个量子比特上的酉算符$A$，$A$对零量子态的作用效果可以表示为：\n",
    "\n",
    "$$\n",
    "A | 0 \\rangle_{n+1}=| \\chi_0 \\rangle_{n+1}\n",
    "=\\sqrt{a}| \\psi_{good} \\rangle_{n}| 1 \\rangle\n",
    "+\\sqrt{1-a}| \\psi_{bad} \\rangle_{n}| 0 \\rangle\n",
    "$$\n",
    "\n",
    "上式中$a \\in [0,1]$是量子振幅，$| \\psi_{good} \\rangle_{n}$和$| \\psi_{bad} \\rangle_{n}$是一对正交归一的由$n$个量子比特表示的量子态，各自对应一个辅助量子比特。\n",
    "\n",
    "设想这样一种情况，存在一个可操作的酉算符$A$，但是我们不知道其对应的量子振幅$a$。量子振幅估算问题，顾名思义，就是估算此酉算符$A$所对应的量子振幅$a$。\n",
    "\n",
    "在含噪中等规模量子 (NISQ) [2] 时代，想要在硬件上更好地实现量子算法，我们需要追求更短的电路深度和更简洁的操作。在此教程中，量子查询复杂度（Quantum query complexity）定义为整个量子电路中应用$A$算符的总次数。通过比较量子查询复杂度（Quantum query complexity）大小，我们可以比较不同估算算法的表现。一般而言，我们希望用更低的量子查询复杂度，实现更高的估算精度。\n",
    "\n",
    "本教程将介绍三种不同的量子振幅估算算法，分别是经典蒙特卡洛方法、最大似然振幅估算（MLAE）[3] 以及变分量子振幅估算（VQAE）。我们将看到在相同的量子查询复杂度下，MLAE算法相比经典蒙特卡洛算法估算精度有优势。VQAE算法则基于MLAE框架的优化，能显著改善MLAE算法电路过深的问题。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 导入相关包\n",
    "import paddle\n",
    "from paddle_quantum.gate import Oracle\n",
    "from paddle_quantum.ansatz import Circuit\n",
    "from paddle_quantum.state import State, zero_state\n",
    "from paddle_quantum.loss import StateFidelity\n",
    "import numpy as np\n",
    "from numpy import pi, log\n",
    "from scipy import optimize\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于$n+1$量子比特的一般情况，$| \\psi_{good} \\rangle_{n}$和$| \\psi_{bad} \\rangle_{n}$为n量子比特展开的$2^n$个基重组构成的一对正交归一量子态。为了更简洁直观，我们考虑单量子比特的情况，将单量子比特展开的2个基$| 0 \\rangle$和$| 1 \\rangle$分别定义为bad state和good state，$A | 0 \\rangle_{1+1}=| \\chi_0 \\rangle_{1+1}=\\sqrt{a}| 1 \\rangle| 1 \\rangle_{anc}+\\sqrt{1-a}| 0 \\rangle| 0 \\rangle_{anc}$。进一步地，在后续用量桨处理时可以略去辅助量子比特，$A | 0 \\rangle_{1}=| \\chi_0 \\rangle_{1}=\\sqrt{a}| 1 \\rangle+\\sqrt{1-a}| 0 \\rangle$。\n",
    "\n",
    "单量子比特的态可以表示为从布洛赫球的球心到球面上一点的向量。在上述情况中，酉算符$A$的效果可以看作对单量子比特态向量在布洛赫球上的旋转。因此，我们可以选择用一个单量子比特$U3$旋转门来构建酉算符$A$。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "酉算符A对应的量子振幅为0.25\n"
     ]
    }
   ],
   "source": [
    "# 定义酉算符A\n",
    "n_qubits = 1 # 考虑单量子比特电路\n",
    "amp_operator = Circuit(n_qubits) # 构建单量子比特酉算符\n",
    "set_param = pi/3 # 酉算符参数\n",
    "amp_param = paddle.to_tensor([set_param, 0, 0], dtype='float32') # 预设酉算符参数\n",
    "amp_operator.u3(param=amp_param) # 将参数输入单比特旋转门上构建酉算符\n",
    "\n",
    "initial_state = zero_state(n_qubits) # 定义初态为零态\n",
    "chi_0_state =amp_operator(initial_state) # 酉算符A作用在零态上的效果\n",
    "quantum_amp =chi_0_state.measure()['1'] # 预设量子振幅\n",
    "print(f\"酉算符A对应的量子振幅为{quantum_amp}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 初代量子振幅估算简介"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d6db7db",
   "metadata": {},
   "source": [
    "Brassard等在2002年提出了初代量子振幅估算算法 [4]，这个算法（$N_{q-AE}\\sim O(1/\\epsilon)$）理论上相比经典蒙卡采样（$N_{q-MC}\\sim O(1/\\epsilon^2)$）实现了平方量子加速。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "量子振幅增大（Quantum amplitude amplification）是Grover搜索算法的拓展，也是解决振幅估算（Amplitude Estimation）问题的基础。\n",
    "\n",
    "考虑一般情况，对于一个作用在$n+1$个量子比特（“+1”为辅助比特）上的酉算符$A$，引入增大算符$Q$:\n",
    "\n",
    "$$\n",
    "Q=-R_{\\chi}R_{good} \\tag{1}\n",
    "$$\n",
    "\n",
    "其中：\n",
    "\n",
    "$$\n",
    "R_{\\chi}=I-2| \\chi_0 \\rangle_{n+1} \\langle\\chi_0|_{n+1}=I-2A| 0 \\rangle_{n+1}\\langle 0|_{n+1}A^\\dagger \\tag{2}\n",
    "$$\n",
    "\n",
    "$$\n",
    "R_{good}=I-2| \\psi_{good} \\rangle_{n} \\langle \\psi_{good}|_n \\otimes | 1 \\rangle\\langle 1 | \\tag{3}\n",
    "$$\n",
    "\n",
    "在以 $| \\psi_{good} \\rangle_{n}| 1 \\rangle$和$| \\psi_{bad} \\rangle_{n}| 0 \\rangle$为正交基所展开的二维子空间$H_\\chi$中，$R_{\\chi}$和$R_{good}$ 均为反射算符。\n",
    "\n",
    "我们可以将$| \\chi_0 \\rangle_{n+1}$看作一个在二维子空间$H_\\chi$中的矢量。\n",
    "\n",
    "$$\n",
    "| \\chi_0 \\rangle_{n+1}=\\cos(\\theta)\n",
    "| \\psi_{bad} \\rangle_{n}| 0 \\rangle+\\sin(\\theta)| \\psi_{good} \\rangle_{n}| 1 \\rangle \\tag{4}\n",
    "$$\n",
    "\n",
    "其中$\\theta$可以认为是矢量$| \\chi_0 \\rangle$和$| \\psi_{bad} \\rangle| 0 \\rangle$所代表的轴之间的夹角。其中我们定义量子振幅为：$a=\\sin^2(\\theta)$。\n",
    "\n",
    "当我们把增大算符$Q$作用在$| \\chi_0 \\rangle_{n+1}$上m次时，得到：\n",
    "\n",
    "$$\n",
    "| \\chi_m \\rangle_{n+1}=Q^m| \\chi_0 \\rangle_{n+1}=\\cos[(2m+1)\\theta]\n",
    "| \\psi_{bad} \\rangle_{n}| 0 \\rangle+\\sin[(2m+1)\\theta]| \\psi_{good} \\rangle_{n}| 1 \\rangle \\tag{5}\n",
    "$$\n",
    "\n",
    "\n",
    "\n",
    "因此我们可以直观地理解，增大算符$Q$对$| \\chi_0 \\rangle_{n+1}$的作用为在空间$H_\\chi$中向$| \\psi_{good} \\rangle_{n}| 1 \\rangle$旋转$2\\theta$角。\n",
    "\n",
    "当选择合适的增大次数$m=\\lfloor \\frac{1}{2}(\\frac{\\pi}{2\\theta}-1)\\rfloor$时，量子振幅$a_m=\\sin[(2m+1)\\theta]\\approx1$。\n",
    "\n",
    "接下来我们基于量桨构建增大算符$Q$。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构造反射算子R_chi\n",
    "identity = paddle.to_tensor([[1, 0],[0, 1]], dtype=\"complex64\") # 定义单位矩阵\n",
    "density_matrix_0 = chi_0_state.ket @ chi_0_state.bra # amp_0_state的密度算符形式\n",
    "r_chi = identity - paddle.to_tensor([2], dtype=\"complex64\") * density_matrix_0 #构建相对chi态的反射算符"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构造反射算子R_good\n",
    "flip = Circuit(n_qubits)\n",
    "flip.x() \n",
    "one_state = flip(initial_state) # 构建“1”量子态，在我们讨论中“1”态定义为good state\n",
    "density_matrix_good = one_state.ket @ one_state.bra # Good state的密度算符\n",
    "r_good = identity - paddle.to_tensor([2], dtype=\"complex64\") * density_matrix_good #构建相对good state的反射算符"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 构造增大算符Q\n",
    "num_amplification = 1 # 增大算符应用次数\n",
    "Q_operator = Oracle(paddle.to_tensor([-1], dtype=\"complex64\") * r_chi @ r_good, qubits_idx=0, num_qubits=1, depth=num_amplification) #利用Oracle构建增大算符，其中深度为应用算符的次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据定义$a = \\sin^2(\\theta)$，所以估算量子振幅$a$可以被转化为估算$\\theta$。我们注意到增大算符$Q=-R_{\\chi}R_{good}=e^{-i2\\theta Y}$，$| \\chi_0 \\rangle_{n+1}$为$Q$的特征向量且特征值为$e^{\\pm2i\\theta}$，所以可以对$Q$进行量子相位估算（quantum phase estimation）来推测$\\theta$的取值，具体量子电路如下图所示。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "76f5e510",
   "metadata": {},
   "source": [
    "![QPE](./figures/VQAE-fig-qpe.png \"图 1: 量子振幅估计电路 [4]。\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "然而如上图所示，初代量子振幅估算算法中使用到的量子相位估计电路包括量子傅里叶变换和多个控制门，这意味着在含噪声的中型量子设备上物理实现初代量子振幅估算是很困难的。所以人们一直在尝试提出更优化的量子振幅估算算法以降低其对量子硬件的要求，便于物理上实现此算法以展示量子优越性。\n",
    "\n",
    "本教程的主题变分量子振幅估算（VQAE）就是最近被提出的一种优化算法。变分量子振幅估算是在最大似然振幅估算（MLAE）的算法框架下，增加了变分近似过程，以控制了MLAE算法所需的量子电路深度，因为更浅的量子电路在物理上更易于实现。VQAE和MLAE相比经典蒙特卡洛方法，都能以更低的量子查询复杂度实现相同的估算精度。\n",
    "\n",
    "所以接下来我们将介绍并用量桨实现经典蒙特卡洛方法、最大似然振幅估算算法和变分量子振幅估算。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 经典蒙特卡洛方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "经典蒙特卡洛方法是指通过重复多次制备态$A| 0 \\rangle_{n+1}=\\sqrt{a}| \\psi_{good} \\rangle_{n}| 1 \\rangle+\\sqrt{1-a}| \\psi_{bad} \\rangle_{n}| 0 \\rangle$并测量辅助量子比特。通过计算测量结果中辅助量子比特为$| 1 \\rangle$态的概率，来估算量子振幅$a$。下面我们用量桨来尝试实现，考虑单量子比特的情况，我们可以选择不引入辅助量子比特。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d8c88075",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "经典蒙特卡洛方法对量子振幅的估算结果是a = 0.24505, 误差绝对值为 0.00495000000000001，相对误差为1.980000000000004%\n",
      "经典蒙特卡洛方法查询复杂度为20000\n"
     ]
    }
   ],
   "source": [
    "# 经典蒙特卡洛方法\n",
    "N_sample_mc = 20000 # 采样总量\n",
    "N_good = 0 # 初始化测得good state的次数\n",
    "for i in range(N_sample_mc):\n",
    "    result = chi_0_state.measure(shots=1) # 单次测量（chi态的构建需要应用一次酉算符A）\n",
    "    N_good += result['1'] # 如果测量结果为1，对应计数加一\n",
    "amp_mc = N_good/N_sample_mc # 通过测量结果为1的概率估算量子振幅a\n",
    "error_mc = abs(amp_mc - quantum_amp) # 估算值与预设值的误差绝对值\n",
    "rate_mc = error_mc/quantum_amp # 估算值的相对误差\n",
    "print(f\"经典蒙特卡洛方法对量子振幅的估算结果是a = {amp_mc}, 误差绝对值为 {error_mc}，相对误差为{100*rate_mc}%\")\n",
    "print(f\"经典蒙特卡洛方法查询复杂度为{N_sample_mc}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4177f22f",
   "metadata": {},
   "source": [
    "经典蒙特卡洛算法作为一种最显而易见的解决方案，可以实现一定精度的振幅估算。估算精度由进行采样的次数决定，更多的采样次数会得到更高精度的振幅估算结果。但我们也注意到，在此方法中每进行一次测量都需要使用一次酉算符$A$来构造$| \\chi_0 \\rangle$态。因此，经典蒙特卡洛算法的查询复杂度等于采样总量。然而我们相信量子振幅估计算法能够提供更优的结果，即使用更低的量子查询复杂度来实现相同的估算精度，这也被称为量子加速（Quantum speedup）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最大似然振幅估算（MLAE）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "相比初代量子振幅估算，最大似然振幅估算算法（MLAE）规避了量子相位估算，通过将多条量子线路合并分析，来进行振幅估算。算法具体步骤如下："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第一步**：选取一个集合$\\{m_k\\}$，此集合中的每一项代表了应用增大算符$Q$的次数，比如$m_k$对应$Q^{m_k}| \\chi_0 \\rangle_{n+1}$。\n",
    "\n",
    "测量$Q^{m_k}| \\chi_0 \\rangle_{n+1}$的辅助量子比特，进而确定量子态属于good state还是bad state。测量得到good state的概率为$\\sin^2((2m_k+1)\\theta_a)$\n",
    "\n",
    "对于态$Q^{m_k}| \\chi_0 \\rangle_{n+1}$我们用$N_k$来表示测量的总次数，$h_k$来表示测得good state的次数。\n",
    "\n",
    "进而我们可以写出对于集合第k项的似然函数：\n",
    "\n",
    "$$\n",
    "L_k(h_k;\\theta_a)=[\\sin^2((2m_k+1)\\theta_a)]^{h_k}\n",
    "[\\cos^2((2m_k+1)\\theta_a)]^{N_k-h_k} \\tag{6}\n",
    "$$\n",
    "\n",
    "**第二步**：将集合$\\{m_0,......,m_M\\}$中每一项对应的似然函数$L_k(h_k;\\theta_a)$合并成一个总似然函数\n",
    "\n",
    "$$\n",
    "L(\\mathbf{h};\\theta_a)= \\prod^{M}_{k=0}L_k(h_k;\\theta_a) \\tag{7}\n",
    "$$\n",
    "\n",
    "其中$\\mathbf{h}=(h_0,h_1,...,h_M)$\n",
    "\n",
    "**第三步**：最大似然振幅估算定义是找到使$L(\\mathbf{h};\\theta_a)$取最大值的$\\theta_a$。故$\\theta_a$的表达式可以写为：\n",
    "\n",
    "$$\n",
    "\\hat{\\theta_a}=\\arg{\\max_{\\theta_a}{L(\\mathbf{h};\\theta_a)}} \\tag{8}\n",
    "=\\arg{\\max_{\\theta_a}{\\text{ln}[L(\\mathbf{h};\\theta_a)]}}\n",
    "$$\n",
    "\n",
    "最终MLAE的结果为：\n",
    "\n",
    "$$\n",
    "\\hat{a}=\\sin^2\\hat{\\theta_a} \\tag{9}\n",
    "$$\n",
    "\n",
    "MLAE的完整过程如下图所示："
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "6dcf46cc",
   "metadata": {},
   "source": [
    "![MLAE](./Figures/VQAE-fig-mlae.png \"MLAE 原理示意图 [3]。\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b34937f2",
   "metadata": {},
   "source": [
    "选择合适的$\\{m_k, N_k\\}$，可以使得估算结果与经典算法对比体现较明显的优势。一般有两种选择方式：\n",
    "\n",
    "1. 线性增加（Linearly incremental sequence, LIS）: $N_k = N_{shot}, \\forall k$，and $m_k = k$. i.e.$m_0=0, m_1=1, ...,m_M=M$\n",
    "  \n",
    "  当$M\\gg1$时，预测误差$\\hat{\\epsilon}\\sim N_q^{-3/4}$，虽然没达到上述提及的最佳情况，但与经典蒙特卡洛方法相比，仍然能体现量子优势。\n",
    "  \n",
    "2. 指数增加（Expoentially incremental sequence, ELS）:$N_k = N_{shot}, \\forall k$，and $m_k = 2^{k-1}$。i.e. $m_0=0, m_1=2^0, ..., m_M=2^{M-1}$\n",
    "  \n",
    "  预测误差$\\hat{\\epsilon}\\sim N_q^{-1}$\n",
    "  \n",
    "\n",
    "在变分量子振幅估算(VQAE)中，用到的是第一种线性增加序列。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7673d10a",
   "metadata": {},
   "source": [
    "### MLAE量桨实现 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25488db9",
   "metadata": {},
   "source": [
    "下面我们用量桨尝试实现最大似然量子振幅估算（MLAE）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 初始化MLAE相关参数（对应于上述教程中的MLAE第一步）\n",
    "M = 25 # 使用增大算符Q的最大次数\n",
    "m = np.arange(0, M, 1) # 线性增加序列 LIS\n",
    "N_k = 25 # 采样总次数\n",
    "h_k = np.zeros(M) # 初始化数据空间以用于存储测得Good state次数\n",
    "\n",
    "# 采样过程\n",
    "for k in range(M):\n",
    "    Q_operator_MLAE = Oracle(paddle.to_tensor([-1], dtype=\"complex64\") * r_chi @ r_good, qubits_idx=0, num_qubits=1, depth=k)\n",
    "    for i in range(N_k):\n",
    "        rotated_state = Q_operator_MLAE(chi_0_state) # 将增大算符作用在initial state上\n",
    "        result = rotated_state.measure(shots = 1) # 测量并统计good state（测得“1”）的次数\n",
    "        h_k[k] += result['1']  # 对于不同的k，记录测得good state的次数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义总似然函数（对数形式）(对应MLAE第二步)\n",
    "params = ()\n",
    "def likelihood(z, *params):\n",
    "    theta = z\n",
    "    f = 0\n",
    "    for i in range(M):\n",
    "        f = f + log(np.sin((2 * m[i] + 1) * theta) ** (2 * h_k[i]) * np.cos((2 * m[i] + 1) * theta) ** (2 * (N_k - h_k[i]))) #相乘转化为ln函数相加\n",
    "    return (-f) # 加负号使得后续算法求得的最小值对应于f的最大值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "总似然函数的极大值为 -241.93038251847616 在theta = 0.5232857156858379 rad时取得\n",
      "MLAE量子振幅估算结果为0.2497289311838693, 估算绝对误差为0.000271068816130704, 相对误差为0.1084275264522816%\n"
     ]
    }
   ],
   "source": [
    "# 使用Brute-force搜索算法来求总似然函数的极值（对应MLAE第三步）\n",
    "rranges = (0, pi/2, pi/200) # Brute-force算法网格点的范围\n",
    "resbrute = optimize.brute(likelihood, (rranges,), args=params, full_output=True, finish=optimize.fmin) #调用Brute-force算法\n",
    "theta_a = resbrute[0][0] # 最小值对应的theta值\n",
    "amp_MLAE = np.sin(theta_a) ** 2 # MLAE量子振幅估算值\n",
    "error_MLAE = abs(amp_MLAE - quantum_amp) # 计算相对预设值的绝对误差\n",
    "rate_MLAE = error_MLAE/quantum_amp # 相对误差\n",
    "print(f\"总似然函数的极大值为 {-resbrute[1]} 在theta = {resbrute[0][0]} rad时取得\")\n",
    "print(f\"MLAE量子振幅估算结果为{amp_MLAE}, 估算绝对误差为{error_MLAE}, 相对误差为{100 * rate_MLAE}%\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据上述算法过程，最大似然量子振幅估算的量子查询复杂度$N_{q-MLAE}$为：\n",
    "\n",
    "$$\n",
    "N_{q-MLAE}=\\sum^{M}_{k=0}N_k(2m_k+1) \\tag{10}\n",
    "$$\n",
    "\n",
    "其中$2m_k$代表着应用$m_k$次增大算符$Q$且每一次应用都需调用一次$A$和一次$A^\\dagger$（$Q = -(I-2A| 0 \\rangle_{n+1} \\langle 0 |_{n+1}A^\\dagger) (I-2| \\psi_{good} \\rangle_{n}\\langle \\psi_{good}|_{n} \\otimes | 1 \\rangle\\langle 1 |) $）；“+1”来自于制备初态 $| \\chi_0 \\rangle_{n+1}$时使用了一次算符$A$ ($| \\chi_0 \\rangle_{n+1}\n",
    "=A| 0 \\rangle_{n+1})$；$N_k$代表对第$k$项的采样次数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MLAE的量子查询复杂度为15625\n"
     ]
    }
   ],
   "source": [
    "# 计算MLAE量子查询复杂度\n",
    "N_q_MLAE = 0\n",
    "for i in range(M):\n",
    "    N_q_MLAE += N_k * (2 * i + 1)\n",
    "print(f\"MLAE的量子查询复杂度为{N_q_MLAE}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最大似然振幅估算与经典蒙特卡洛对比"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对同一个酉算符$A$的振幅估算问题，分别使用最大似然振幅估算和经典蒙特卡洛算法。比较两个算法估算误差$\\epsilon$与查询复杂度$N_q$之间的关系。例如，设定酉算符的输入参数为$\\pi/8$，保持两算法量子查询复杂度相同，比较估算值误差大小。数值实验结果如下图所示："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![comparison](./Figures/VQAE-fig-comparison.png \"图 3: MLAE 和 CMC 算法表现对比。\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上图体现了MLAE算法在相同的量子查询复杂度下，估算误差大约比经典蒙特卡洛算法小一个数量级。这个结果体现了MLAE相比经典蒙特卡洛算法的优越性。当估算量子振幅越小时，MLAE相较经典蒙特卡洛的优势会越明显。读者可根据上文已提供的算法代码自行尝试验证。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b86a83e",
   "metadata": {},
   "source": [
    "## 变分量子振幅估算（VQAE） "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bab7472",
   "metadata": {},
   "source": [
    "基于使用线性增大序列（LIS）$\\{m=1,2,3,...,M\\}$的MLAE算法的量子电路深度以$2m+1$的趋势增长。量子电路深度过大会增大其物理实现难度，所以提出了VQAE算法 [1] 来防止线路深度随$m$无限地增长。\n",
    "\n",
    "VQAE基于MLAE的算法框架增加了一个变分过程（variational step）。态$| \\chi_m \\rangle_{n+1}$会周期性地近似为一个深度为1的变分量子态。对于MLAE算法中的线性增加序列，我们选择一个正整数$k$作为变分周期，每到达$Q^k\\ (0<k<M)$就进行一次变分近似过程。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6dadbc7e",
   "metadata": {},
   "source": [
    "### VQAE的算法结构（伪代码）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![pesudo](./Figures/VQAE-fig-pesudo.png \"图 4: VQAE 伪代码。\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f167e02",
   "metadata": {},
   "source": [
    "使用得到的$\\{h_m\\}$，计算每一项的似然函数$L_m(h_m;\\theta_a)$，继续进行最大似然近似。\n",
    "\n",
    "由与MLAE相同的步骤，我们可以得到振幅估算为：\n",
    "\n",
    "$$\n",
    "\\hat{\\theta_a}\n",
    "=\\arg{\\max_{\\theta_a}{\\text{ln}[L(\\{h_m\\};\\theta_a)]}} \\tag{11}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2832b3c5",
   "metadata": {},
   "source": [
    "### 变分近似过程"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8642bfcb",
   "metadata": {},
   "source": [
    "变分近似是VQAE算法中的核心步骤。在这个过程中，设变分周期为$k$，我们将一个线路深度为$2k+1$的态$Q^k | \\phi_i \\rangle_{n+1}$（目标态）用线路深度为1的变分量子态 $| \\phi_{var}(\\mathbf{\\lambda}) \\rangle_{n+1}$近似替换，其中$\\mathbf{\\lambda}$代表若干变分参数。\n",
    "\n",
    "我们希望目标态$Q^k | \\phi_i \\rangle_{n+1}$和变分量子态$| \\phi_{var}(\\mathbf{\\lambda}) \\rangle_{n+1}$尽可能接近，我们用目标态和变分量子态之间的保真度来衡量这两个态的相似程度，保真度$F(\\lambda)$定义为:\n",
    "\n",
    "$$\n",
    "F(\\lambda)=Re[\\langle \\phi_{var}(\\mathbf{\\lambda})|_{n+1}Q^k | \\phi_i \\rangle_{n+1}] \\tag{12}\n",
    "$$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "变分近似的最优解可以写为:\n",
    "\n",
    "$$\n",
    "| \\phi_{i+1} \\rangle_{n+1}=| \\phi_{var}(\\tilde{\\mathbf{\\lambda}}) \\rangle_{n+1} \n",
    "\\quad\n",
    "\\tilde{\\mathbf{\\lambda}}=\\arg{\\max_{\\mathbf{\\lambda}}{F(\\mathbf{\\lambda})}} \\tag{13}\n",
    "$$\n",
    "\n",
    "在代码实践中，我们可以将非保真度 $\\text{Infidelity}(\\lambda) = 1 - F(\\lambda)$ 定义为损失函数，并用Adam优化器寻找使损失函数最小的参数值。损失函数取最小值时保真度取最大值，对应变分量子态和目标态最接近的情况。注意到这里计算损失函数的量子线路深度为$2k+2$，为整个VQAE算法中线路深度最大的部分。\n",
    "\n",
    "变分量子态$| \\phi_{var}(\\mathbf{\\lambda}) \\rangle_{n+1}$为一个参数化量子线路（PQC）,可以表示为：\n",
    "\n",
    "$$\n",
    "\\left|\\phi_{\\text {var }}(\\boldsymbol{\\lambda})\\right\\rangle_{n+1}=\\mathcal{U}_{\\text {var }}(\\boldsymbol{\\lambda})\\left|\\phi_{\\text {init }}\\right\\rangle_{n+1}\n",
    "=\\prod_{j} e^{-\\mathrm{i} \\lambda_{j} G_{j}}\\left|\\phi_{\\text {init }}\\right\\rangle_{n+1} \\tag{14}\n",
    "$$\n",
    "\n",
    "后续代码实践中，变分量子态为单量子比特参数化量子电路，每一层由一个$R_y(\\theta)$单比特旋转门和$R_z(\\theta)$单比特旋转门组成。变分量子态的初态为$| \\phi_{\\text{init}} \\rangle_{n+1}=| \\chi_0 \\rangle_{n+1}$，变分周期为5。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cfdae51",
   "metadata": {},
   "source": [
    "### VQAE量桨实现"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3997e65",
   "metadata": {},
   "source": [
    "接下来我们尝试用量桨实现变分量子振幅估算（VQAE）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义VQAE算法中用到的函数\n",
    "\n",
    "def construct_Q(input_param: float, n_qubits: int, num_amplification):\n",
    "    r\"\"\" 构建增大算符Q\n",
    "    \n",
    "    Args:\n",
    "        input_param: 输入参数, 用于U3旋转门\n",
    "        n_qubits: 线路量子比特数\n",
    "        num_amplification: 使用增大算符的次数\n",
    "    \n",
    "    Returns:\n",
    "        Oracle: 对应参数和深度的增大算符\n",
    "    \n",
    "    \"\"\"\n",
    "    # 定义酉算符A\n",
    "    amp_operator = Circuit(n_qubits) \n",
    "    amp_param = paddle.to_tensor([input_param, 0, 0], dtype='float32') #预设酉算符参数\n",
    "    amp_operator.u3(param=amp_param)\n",
    "\n",
    "    initial_state = zero_state(n_qubits) # 定义初态为零态\n",
    "    chi_0_state =amp_operator(initial_state) # 酉算符A作用在零态上的效果\n",
    "\n",
    "    # 构造反射算子R_chi\n",
    "    identity = paddle.to_tensor([[1, 0],[0, 1]], dtype=\"complex64\") # 定义单位矩阵\n",
    "    density_matrix_0 = chi_0_state.ket @ chi_0_state.bra # amp_0_state的密度算符形式\n",
    "    r_chi = identity - paddle.to_tensor([2], dtype=\"complex64\") * density_matrix_0\n",
    "\n",
    "    # 构造反射算子R_good\n",
    "    flip = Circuit(n_qubits)\n",
    "    flip.x()\n",
    "    one_state = flip(initial_state) #构建“1”量子态，在我们讨论中“1”态定义为good state\n",
    "    density_matrix_good = one_state.ket @ one_state.bra #Good state的密度算符\n",
    "    r_good = identity - paddle.to_tensor([2], dtype=\"complex64\") * density_matrix_good\n",
    "    \n",
    "    # 返回增大算符Q\n",
    "    return Oracle(paddle.to_tensor(paddle.to_tensor([-1], dtype=\"complex64\") * r_chi @ r_good), qubits_idx=0, num_qubits=n_qubits, depth=num_amplification)\n",
    "\n",
    "\n",
    "def loss_fcn(input_state: State, period: int, start_state: State, target_param: float) -> paddle.Tensor:\n",
    "    r\"\"\" 计算神经网络的损失函数\n",
    "    \n",
    "    Args:\n",
    "        input_state: 输入态\n",
    "        period: 变分周期\n",
    "        start_state: 当前变分态，用于构建目标态\n",
    "        target_param: 目标态参数\n",
    "    \n",
    "    Returns:\n",
    "        loss: 损失函数值, 损失函数定义为输入态和目标态之间的非保真度(Infidelity)\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    Q_var = construct_Q(target_param, int(1), period)\n",
    "    Target_state = Q_var(start_state) \n",
    "    loss = 1 - StateFidelity(Target_state)(input_state)\n",
    "    return loss\n",
    "\n",
    "\n",
    "def cir_constructor(depth: int) -> Circuit:\n",
    "    r\"\"\" 构建变分量子电路\n",
    "    \n",
    "    Args:\n",
    "        depth: 电路深度\n",
    "    \n",
    "    Returns:\n",
    "        变分量子电路\n",
    "    \n",
    "    Note:\n",
    "        单量子比特, 一层定义为Ry和Rz任意角度旋转门, 旋转角度为电路参数, 变分量子电路深度为3\n",
    "    \n",
    "    \"\"\"\n",
    "    cir = Circuit(1)\n",
    "    \n",
    "    for _ in range(depth):\n",
    "        cir.ry()\n",
    "        cir.rz()\n",
    "    return cir"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 初始化相关参数（注：VQAE仍使用MLAE框架）\n",
    "M = 25 # 使用增大算符Q的最大次数\n",
    "m = np.arange(0, M, 1) # 线性增加序列 LIS\n",
    "N_k_vqae = 50 # 采样总次数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<paddle.fluid.core_noavx.Generator at 0x7fd89399e930>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 变分近似定义\n",
    "# 超参数设置\n",
    "theta_size = 6 # 线路深度决定的参数数量\n",
    "ITR = 500  # 设置迭代次数\n",
    "LR = 0.001  # 设置学习速率\n",
    "SEED = 1  # 固定随机数种子\n",
    "paddle.seed(SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=================================\n",
      "第 1 次变分近似\n",
      "损失函数的最小值是:  0.011207818984985352\n",
      "变分参数值为 [-0.3985748  4.4845576  3.8463612  0.5077383  2.1137552  5.696977 ]\n",
      "变分态相比目标态的保真度为0.9888777136802673\n",
      "=================================\n",
      "第 2 次变分近似\n",
      "损失函数的最小值是:  0.022154152393341064\n",
      "变分参数值为 [3.5385787 3.686828  3.778493  0.8545992 3.3457727 5.151529 ]\n",
      "变分态相比目标态的保真度为0.9780024886131287\n",
      "=================================\n",
      "第 3 次变分近似\n",
      "损失函数的最小值是:  0.12489771842956543\n",
      "变分参数值为 [2.9717565 4.5942483 3.8417864 1.0915956 2.9404602 4.45632  ]\n",
      "变分态相比目标态的保真度为0.8756691813468933\n",
      "=================================\n",
      "第 4 次变分近似\n",
      "损失函数的最小值是:  0.07246685028076172\n",
      "变分参数值为 [5.293609  5.0283127 1.7944657 3.575252  2.10594   4.7431984]\n",
      "变分态相比目标态的保真度为0.9278923273086548\n",
      "=================================\n",
      "第 5 次变分近似\n",
      "损失函数的最小值是:  0.007037162780761719\n",
      "变分参数值为 [ 2.9615374   6.2987323   2.9560285  -0.05320463  1.5106332   3.6751766 ]\n",
      "变分态相比目标态的保真度为0.993030846118927\n"
     ]
    }
   ],
   "source": [
    "# 采样和变分近似过程\n",
    "start_state = chi_0_state # start_state是变分量子态，算法开始时为chi_0_state\n",
    "cycle = 5 # 触发变分近似的周期\n",
    "h_k_vqae = np.zeros(M) # 初始化数据空间以用于存储测得Good state次数\n",
    "for k in range(M):\n",
    "    i = np.floor(k / cycle)\n",
    "    j = k % cycle\n",
    "    Q_operator_VQAE = construct_Q(set_param, int(1), j)\n",
    "    for sample in range(N_k_vqae):\n",
    "        rotated_state = Q_operator_VQAE(start_state) # 将增大算符作用在变分态上\n",
    "        result = rotated_state.measure(shots = 1) # 测量并统计good state（测得“1”）的\n",
    "        h_k_vqae[k] += result['1']  # 对于不同的k，测得good state的次数\n",
    "\n",
    "    if j == cycle - 1: # 触发变分近似过程的条件\n",
    "        # 记录中间优化结果\n",
    "        loss_list = []\n",
    "\n",
    "        # 定义变分电路\n",
    "        cir = cir_constructor(3)\n",
    "\n",
    "        # 利用Adam优化器.\n",
    "        opt = paddle.optimizer.Adam(learning_rate=LR, parameters=cir.parameters())\n",
    "        \n",
    "        # 优化循环\n",
    "        for itr in range(ITR):\n",
    "            # 向前传播计算损失函数\n",
    "            loss = loss_fcn(cir(chi_0_state), cycle, start_state, set_param)\n",
    "\n",
    "            # 反向传播优化损失函数\n",
    "            loss.backward()\n",
    "            opt.minimize(loss)\n",
    "            opt.clear_grad()\n",
    "\n",
    "            # 记录学习曲线\n",
    "            loss_list.append(loss.item())\n",
    "        \n",
    "        print(\"=================================\")\n",
    "        print(f'第 {int(i + 1)} 次变分近似')\n",
    "        print(f'损失函数的最小值是:  {loss_list[-1]}')\n",
    "        print(f\"\\r变分参数值为 {cir.param.numpy()}\")\n",
    "        \n",
    "        Q_test = construct_Q(set_param, int(1), cycle)\n",
    "        test_state = Q_test(start_state) # 更新用于计算保真度的测试态\n",
    "        \n",
    "        start_state = cir(chi_0_state)  # 更新变分量子态\n",
    "        start_state.data.stop_gradient = True \n",
    "        print(f\"变分态相比目标态的保真度为{StateFidelity(test_state)(start_state).numpy()[0]}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义总似然函数（对数形式）(对应MLAE第二步)\n",
    "params = ()\n",
    "def likelihood_vqae(z, *params):\n",
    "    theta = z\n",
    "    f = 0\n",
    "    for i in range(M):\n",
    "        f = f + log(np.sin((2 * m[i] + 1) * theta) ** (2 * h_k_vqae[i]) * np.cos((2 * m[i] + 1) * theta) ** (2 * (N_k_vqae - h_k_vqae[i]))) #相乘转化为ln函数相加\n",
    "    return (-f) # 加负号使得后续算法求得的最小值对应于f的最大值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=================================\n",
      "总似然函数的极大值为 -691.84028156814 在theta = 0.532245313972681 rad时取得\n",
      "VQAE量子振幅估算结果为0.2575251290528533, 估算绝对误差为0.007525129052853297, 相对误差为3.0100516211413186%\n"
     ]
    }
   ],
   "source": [
    "# 使用Brute-force搜索算法来求总似然函数的极值（对应MLAE第三步）\n",
    "rranges = (0, pi/2, pi/200) # Brute-force算法网格点的范围\n",
    "resbrute = optimize.brute(likelihood_vqae, (rranges,), args=params, full_output=True, finish=optimize.fmin) #调用Brute-force算法\n",
    "theta_a = resbrute[0][0] # 最小值对应的theta值\n",
    "amp_VQAE = np.sin(theta_a) ** 2 # MLAE量子振幅估算值\n",
    "error_VQAE = abs(amp_VQAE - quantum_amp) # 计算相对预设值的绝对误差\n",
    "rate_VQAE = error_VQAE/quantum_amp # 相对误差\n",
    "print(\"=================================\")\n",
    "print(f\"总似然函数的极大值为 {-resbrute[1]} 在theta = {resbrute[0][0]} rad时取得\")\n",
    "print(f\"VQAE量子振幅估算结果为{amp_VQAE}, 估算绝对误差为{error_VQAE}, 相对误差为{100 * rate_VQAE}%\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由此可得，VQAE算法也实现了精度较高的振幅估算，与原MLAE算法相比最大量子电路深度显著减小。例如，考虑M=50且变分周期为5的情况，MLAE算法最多需要对$| \\chi_0 \\rangle$连续应用50次增大算符$Q$，而VQAE算法的量子电路最多连续应用5次，为MLAE的十分之一。这说明使用VQAE算法可以有效地减少量子电路深度，有助于量子振幅估算在NISQ设备上实现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "VQAE算法的量子查询复杂度由变分复杂度$N_{var}$和采样复杂度$N_{samp}$两部分组成。\n",
    "$$\n",
    "N = N_{var} + N_{samp} \\tag{15}\n",
    "$$\n",
    "$$\n",
    "N_{var} = N_{var/1}(2k+2)\\lfloor M/k \\rfloor  \\sim O(k\\lfloor M/k \\rfloor) \\tag{16}\n",
    "$$\n",
    "$$\n",
    "N_{samp} = hk(k+2)\\lfloor M/k \\rfloor + h(M\\%k)(M\\%k+2) \\tag{17}\n",
    "$$\n",
    "其中$M$为MLAE线性增大序列中的最大值，$k$为VQAE中的变分周期，$h$为采样过程中对每个态重复采样的次数。$N_{var/1}=2n_fn_sn_p$, 一次变分过程中需要运行的量子电路总量，其中$n_p$为参数化量子电路的参数数量，$n_s$是参数化量子电路的参数扫描次数，$n_f$是每次计算目标函数时伯努利试验的次数（在硬件实现中可以认为约等于$n_s$）。具体分析可查看参考文献[1]。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "采样复杂度为 8750\n",
      "变分复杂度为 180000000\n",
      "VQAE算法的量子查询复杂度为 180008750\n"
     ]
    }
   ],
   "source": [
    "# 计算VQAE量子查询复杂度\n",
    "from math import floor\n",
    "M_vqae = M\n",
    "k_cycle = cycle\n",
    "n_p = theta_size\n",
    "n_s = ITR\n",
    "n_f = n_s\n",
    "N_var1 = 2 * n_p * n_s * n_f\n",
    "N_var = N_var1 * (2 * k_cycle + 2) * floor(M_vqae/k_cycle)\n",
    "N_samp = N_k_vqae * k_cycle * (k_cycle + 2) * floor(M_vqae/k_cycle) + N_k_vqae * (M_vqae % k_cycle) * (M_vqae % k_cycle + 2)\n",
    "print(f\"采样复杂度为 {N_samp}\")\n",
    "print(f\"变分复杂度为 {N_var}\")\n",
    "print(f\"VQAE算法的量子查询复杂度为 {N_var + N_samp}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们注意到VQAE算法的量子查询复杂度很高，其主要来自于变分近似过程的复杂度。这是减少量子电路深度所引入的代价。引入的变分过程并非越多越好，量子电路的深度和变分过程的复杂度之间存在一个权衡关系。但是可以通过一些优化设计，降低变分近似过程中的量子查询复杂度。比如文献[1]中提到的Adaptive VQAE，感兴趣的读者可自行参看。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 总结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本教程主要内容为用量桨实现变分量子振幅估算（VQAE）。教程首先介绍了量子振幅估算问题和初代算法物理实现的难度。进而介绍了最大似然振幅估算（MLAE），MLAE规避了初代算法主要的物理实现难点——量子相位估算，但是存在量子电路深度过大的问题，也不利于物理实现。为了降低MLAE算法的量子电路深度，我们引入了一个变分近似过程得到了变分量子振幅估算，VQAE相比MLAE可以显著降低量子电路的深度。VQAE算法的提出进一步提高了量子振幅估算物理实现的可能性。但同时需注意，引入变分过程时会带来大量变分复杂度，变分过程和量子电路深度之间存在权衡关系。\n",
    "\n",
    "教程基于量桨实现了单量子比特的MLAE和VQAE，展示了对预设量子振幅的低误差预测。并且比较了上述算法与经典蒙特卡洛算法的预测精度和量子查询复杂度，通过数值实验展示了量子算法相比经典算法的加速效应。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_______\n",
    "## 参考文献"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[1] Plekhanov, Kirill, et al. \"Variational quantum amplitude estimation.\" Quantum 6 (2022): 670. https://quantum-journal.org/papers/q-2022-03-17-670/\n",
    "\n",
    "[2] Preskill, John. \"Quantum computing in the NISQ era and beyond.\" Quantum 2 (2018): 79. https://quantum-journal.org/papers/q-2018-08-06-79/\n",
    "\n",
    "[3] Suzuki, Yohichi, et al. \"Amplitude estimation without phase estimation.\" Quantum Information Processing 19.2 (2020): 1-17. https://link.springer.com/article/10.1007/s11128-019-2565-2\n",
    "\n",
    "[4] Brassard, Gilles, et al. \"Quantum amplitude amplification and estimation.\" Contemporary Mathematics 305 (2002): 53-74. https://arxiv.org/pdf/quant-ph/0005055.pdf"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7.13 ('py3.7_pq2.2.1')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.13"
  },
  "vscode": {
   "interpreter": {
    "hash": "4e4e2eb86ad73936e915e7c7629a18a8ca06348106cf3e66676b9578cb1a47dd"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
